﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 红黑树
{
    class RBTree
    {
        public RBTreeNode rootnode;   //根及节点

        public void Insert(int item)  //插入
        {
            if (rootnode == null)
            {
                rootnode = new RBTreeNode(item, Color.black);
            }
            else
            {
                //这一步只完成插入操作，与二叉查找的插入一样
                var newnode = Inserts(item);

                //重点在于这一步 看节点是否需要调整
                InsertFixUp(newnode);
            }
        }
        public RBTreeNode Inserts(int item)   //正常二叉树插入
        {
            var node = rootnode;
            var newnode = new RBTreeNode(item, Color.red);  //插入的初始颜色为红
            while (true)
            {
                if (item > node.key)
                {
                    if (node.right == null)
                    {
                        //注意父子关系要确定
                        newnode.parent = node;
                        node.right = newnode;
                        break;
                    }
                    node = node.right;
                }else if (item < node.key)
                {
                    if (node.left == null)
                    {
                        newnode.parent = node;
                        node.left = newnode;
                        break;
                    }
                    node = node.left;
                }
            }
            return newnode;
        }

        //红黑树的关键操作，如何平衡红黑树
        //插入节点的初始颜色为红，如果父节点为黑则不要平衡操作，除此之外
        //红黑树插入节点的情况可以分为以下两种；
        //1、叔节点为红；祖父，父叔，当前节点，三者关系为“黑红红”改为“红黑红”即可，但是调整后的祖父节点可能不平衡，再对祖父节点InsertFinxUp递归平衡
        //2、叔节点为黑或者空：需要旋转具体左旋还是右旋需要根据当前节点在父节点的左子树还是右子树来确定
        private void InsertFixUp(RBTreeNode node)
        {
            var parentnode = node.parent;
            //显然插入节点的父节点存在且为红我们才需要平衡
            if (parentnode != null && parentnode.color == Color.red)
            {
                var gparent = parentnode.parent;

                //如果父节点是祖父节点的左子节点
                if (parentnode == gparent.left)
                {
                    var unclenode = gparent.right;
                    //第一种情况
                    //叔节点存在且为红色，只需要修改颜色，然后对祖父节点递归
                    if (unclenode != null && unclenode.color == Color.red) 
                    {
                        setRed(gparent);
                        setBlack(parentnode);
                        setBlack(unclenode);
                        InsertFixUp(gparent);
                    }
                    else    //第二种情况   如果叔节点不为红或者不存在 ， 那么就是分为左旋还是右旋
                    {
                        //类似AVL中的LL型 右旋
                        if (node == parentnode.left)
                        {
                            setBlack(parentnode);
                            setRed(gparent);
                            Rightrotate(gparent);
                        }
                        else if (node == parentnode.right) //类似LR  先对父节点左旋 在吧父节点当新插入的节点
                        {
                            LeftRotate(parentnode);
                            InsertFixUp(parentnode);
                        }
                    }
                }
                else
                {
                    //如果父节点是祖父节点的右子节点
                    var unclenode = gparent.left;
                    if (unclenode != null && unclenode.color == Color.red) 
                    {
                        setBlack(parentnode);
                        setBlack(unclenode);
                        setRed(gparent);
                        InsertFixUp(gparent);
                    }
                    else
                    {
                        if (node == parentnode.right)
                        {
                            setBlack(parentnode);
                            setRed(gparent);
                            LeftRotate(gparent);
                        }
                        else if (node == parentnode.left) 
                        {
                            Rightrotate(parentnode);
                            InsertFixUp(parentnode);
                        }
                    }
                }
            }
            setBlack(rootnode);
        }
        private void LeftRotate(RBTreeNode node)
        {
            //子树的左旋    node = p
            //            g                                 g
            //            |                                 |                  
            //            p                                cur
            //          /   \          ===>               /   \  
            //         X3   cur                          p     X2 
            //             /   \                       /   \ 
            //            X1   X2                     X3    X1
            //

            // 这里的旋转操作比AVL树复杂  ， 因为需要交换父节点之间关系
            var temp = node.right;      //temp = cur
            node.right = temp.left;     //p的右孩子设置为cur的左孩子
            if (temp.left != null)      
            {
                temp.left.parent = node;  //不为空就认父
            }

            temp.parent = node.parent;    //cur的父改成g
            if (node.parent == null)      //没有g说明p就是根结点
            {
                rootnode = temp;
            }
            else
            {
                if (node == node.parent.left)   //p在g的左孩子
                {
                    node.parent.left = temp;
                }
                else
                {
                    node.parent.right = temp;
                }
            }
            temp.left = node;           //cur的左孩子设置成p
            node.parent = temp;         //p的父改成cur

        }
        private void Rightrotate(RBTreeNode node)
        {
            //子树的右旋    node = p
            //            g                                 g
            //            |                                 |                  
            //            p                                cur
            //          /   \          ===>               /   \  
            //         cur  X3                           X1    P 
            //        /   \                                  /   \ 
            //       X1   X2                                X2    X3
            //


            var temp = node.left;
            node.left = temp.right;

            if (temp.right != null)
            {
                temp.right.parent = node;
            }
            temp.parent = node.parent;
            if (node.parent == null)
            {
                rootnode = temp;
            }
            else
            {
                if (node == node.parent.left)
                {
                    node.parent.left = temp;
                }else if (node == node.parent.right)
                {
                    node.parent.right = temp;
                }
            }
            temp.right = node;
            node.parent = temp;
        }

        public void setBlack(RBTreeNode node)
        {
            node.color = Color.black;
        }
        public void setRed(RBTreeNode node)
        {
            node.color = Color.red;
        }
        public void LayerOrder(RBTreeNode rootnode)
        {
            //优雅的层序遍历
            RBTreeNode current = rootnode;
            Queue<RBTreeNode> queue = new Queue<RBTreeNode>();
            queue.Enqueue(rootnode);
            while (queue.Any())
            {
                var temp = queue.Dequeue();
                //这里默认调用tostring()
                Console.Write(temp + " ");
                if(temp.left != null)
                {
                    queue.Enqueue(temp.left);
                }
                if (temp.right != null)
                {
                    queue.Enqueue(temp.right);
                }
            }
        }
    }
}
